package com.faiz.algorithm;

public class FindTargetSumWays {
    private int res;
    private int l;
    private int target;
    private int[] nums;

    public int findTargetSumWays(int[] nums, int target) {
        // 使用回溯法来进行操作
        res = 0;
        this.l = nums.length;
        this.target = target;
        this.nums = nums;
        backTrace(0, 0);
        return res;
    }

    private void backTrace(int sum, int index) {
        if (index == l) {
            if (sum == target) res++;
            return;
        }

        if (index < l) {
            sum += nums[index];
            backTrace(sum, index + 1);
            sum -= nums[index];

            sum -= nums[index];
            backTrace(sum, index + 1);
            sum += nums[index];
        }
    }

    public static void main(String[] args) {
        FindTargetSumWays findTargetSumWays = new FindTargetSumWays();
        int[] nums = {1, 1, 1, 1, 1};
        int target = 3;
        System.out.println(findTargetSumWays.findTargetSumWays(nums, target));
    }
}
